Efficient and reliable data storage and communication requires practical encoding and decoding methods for error-correcting codes. It is known that low density parity check (LDPC) codes with belief propagation (BP) decoding provide performance close to the Shannon limit. In particular, irregular LDPC codes are among the best for many applications. Various irregular LDPC codes have been accepted or being considered for various communication and storage standards, such as DVB/DAB, wireline ADSL, IEEE 802.11n, and IEEE 802.16. However, it is known that the performance of irregular LDPC decoders is less than optimal.
Although BP decoding for these LDPC codes provides excellent performance, it is too complex for hardware implementation. BP decoding can be simplified by a check node processor with a simple minimum operation, resulting in a min-sum decoding method. While the min-sum decoding method is less complex to implement, it has decreased performance compared to BP decoding. The min-sum decoding method can be improved by linear post-normalization at a check node processor, which is called the normalized min-sum decoding method. Nevertheless, there is still a big gap between the performance of the normalized min-sum decoding method and BP decoding, especially for decoding irregular LDPC codes.
LDPC Codes
LDPC codes were first described by Gallager in the 1960s. LDPC codes perform remarkably close to Shannon limit. A binary (N, K) LDPC code, with a code length N and dimension K, is defined by a parity check matrix H of (N-K) rows and N columns. Most entries of the matrix H are zeros and only a small number the entries are ones, hence the matrix H is sparse. Each row of the matrix H represents a check sum, and each column represents a variable, e.g., a bit or symbol. The LDPC codes described by Gallager are regular, i.e., the parity check matrix H has constant-weight rows and columns.
In 1993, similar iterative methods were shown to perform very well for a new class of codes known as “turbo-codes.” The success of turbo-codes was partially responsible for greatly renewed interest in LDPC codes and iterative decoding methods. There has been a considerable amount of recent work to improve the performance of iterative decoding methods for both turbo-codes and LDPC codes, and other related codes such as “turbo product codes” and “repeat-accumulate codes.” For example, a special issue of the IEEE Communications Magazine was devoted to this work in August 2003. For an overview, see C. Berrou, “The Ten-Year-Old Turbo Codes are entering into Service,” IEEE Communications Magazine, vol. 41, pp. 110-117, August 2003 and T. Richardson and R. Urbanke, “The Renaissance of Gallager's Low-Density Parity Check Codes,”IEEE Communications Magazine, vol. 41, pp. 126-131, August 2003.
Regular LDPC codes can be extended to irregular LDPC codes, in which the weight of rows and columns vary. An irregular LDPC code is specified by degree distribution polynomials v(x) and c(x), which define the variable and check node degree distributions, respectively. More specifically, let
                                          v            ⁡                          (              x              )                                =                                    ∑                              j                =                1                                            d                                  v                  ⁢                                                                          ⁢                  max                                                      ⁢                                          v                j                            ⁢                              x                                  j                  -                  1                                                                    ,                            (        1        )                        and                                                                            c            ⁡                          (              x              )                                =                                    ∑                              j                =                1                                            d                                  c                  ⁢                                                                          ⁢                  max                                                      ⁢                                          c                j                            ⁢                              x                                  j                  -                  1                                                                    ,                            (        2        )            where the variables dv max and dc max are a maximum variable node degree and a maximum check node degree, respectively, and vj(cj) represents the fraction of edges emanating from variable (check) nodes of degree j. It has been shown, both theoretically and empirically, that with properly selected degree distributions, irregular LDPC codes outperform regular LDPC codes.
The regular and irregular LDPC codes can be decoded by hard-decision, soft-decision and hybrid-decision methods. The best soft decision decoding is BP, which gives the best error performance of LDPC codes.
BP Decoding
As shown in FIG. 1 for conventional BP decoding, the check node processor 110 and a bit node processor 120 operate serially while passing reliability messages to each other based on the belief propagation principle, where Uch 130 is a log-likelihood ratio from channel. The main difficulty for a practical implementation of a BP decoder arises from the check processor, in which a “tanh” function requires very high computational complexity.
We denote the set of bits that participate in check m by N(m), and the set of checks in which bit n participates by M(n). We also denote N(m)\n as the set N(m) with bit n excluded, and M(n)\m as the set M(n) with check m excluded.
We define the following notations associated with ithiteration:
Uch,n: the log-likelihood ratios (LLR) of bit n which is generated by the channel output,
Umn(i): the LLR of bit n which is sent from check m to bit node n,
Vmn(i): The LLR of bit n which is sent from bit node n to check node m, and
Vn(i): the a posteriori LLR of bit n computed at each iteration.
The conventional BP decoding method includes the following steps:
Initialization                Set i=1 and the maximum number of iterations to Imax. For each m and n, set Vmn(0)=Uch,n.        
Step 1
Horizontal step, for 1≦n≦N and each m ∈ M(n), process:
                              U          mn                      (            i            )                          =                  log          ⁢                                                    1                +                                                      ∏                                                                  n                        ′                                            ∈                                                                        N                          ⁡                                                      (                            m                            )                                                                          ⁢                        \                        ⁢                                                                                                  ⁢                        n                                                                              ⁢                                      tanh                    ⁡                                          (                                                                        V                                                      mn                            ′                                                                                (                                                          i                              -                              1                                                        )                                                                          /                        2                                            )                                                                                                  1                -                                                      ∏                                                                  n                        ′                                            ∈                                                                        N                          ⁡                                                      (                            m                            )                                                                          ⁢                        \                        ⁢                                                                                                  ⁢                        n                                                                              ⁢                                      tanh                    ⁡                                          (                                                                        V                                                      mn                            ′                                                                                (                                                          i                              -                              1                                                        )                                                                          /                        2                                            )                                                                                            .                                              (        3        )            
Vertical step, for 1≦n≦N and each m ∈ M(n), process
                                          V            mn                          (              i              )                                =                                    U                              ch                ,                n                                      +                                          ∑                                                      m                    ′                                    ∈                                                            M                      ⁡                                              (                        n                        )                                                              ⁢                    \                    ⁢                                                                                  ⁢                    m                                                              ⁢                              U                                                      m                    ′                                    ⁢                  n                                                  (                  i                  )                                                                    ,        and                            (        4        )                                          V          n                      (            i            )                          =                              U                          ch              ,              n                                +                                    ∑                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                        ⁢                                          U                mn                                  (                  i                  )                                            .                                                          (        5        )            
Step 2                Hard decision and termination criterion test. Generate Ŵ(i)=[Ŵn(i)], such that Ŵn(i)=1 for Vn(i)>0, and ŵn(i)=0 otherwise. If Hŵ(i)=0, or the maximum number of iterations is reached, then output ŵ(i) as the decoded codeword and terminate the decoding iteration, otherwise, set i=i+1, and go to Step 1.        
Step 3                Output ŵ(i) as the decoded codeword.        
Min-sum Decoding
As shown in FIG. 2, conventional min-sum decoding simplifies the conventional BP decoding in the check node processor 210 by approximating the product of tanh functions as a min-sum operation. The updating rule in the check node of min-sum is modified as:
                              U          mn                      (            i            )                          =                              ∏                                          n                ′                            ∈                                                N                  ⁡                                      (                    m                    )                                                  ⁢                \                ⁢                                                                  ⁢                n                                              ⁢                                    sgn              ⁡                              (                                  V                                      mn                    ′                                                        (                                          i                      -                      1                                        )                                                  )                                      ×                                          min                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              ⁢                    \                    ⁢                                                                                  ⁢                    n                                                              ⁢                                                                                      V                                          mn                      ′                                                              (                                              i                        -                        1                                            )                                                                                        .                                                                        (        6        )            
Min-sum decoding is possible in hardware because only comparison and addition operations are needed. Nevertheless, the conventional min-sum decoding has decreased performance.
Conventional Normalized Min-Sum Decoding
As shown in FIG. 3, conventional normalized min-sum decoding improves the min-sum decoding by normalizing 310 the messages generated by the check node processor 210, where ‘A’ 300 denotes the normalization factor. The updating rule in the check node of normalized min-sum decoding is as follows:
                              U          mn                      (            i            )                          =                  A          ⁢                                    ∏                                                n                  ′                                ∈                                                      N                    ⁡                                          (                      m                      )                                                        ⁢                  \                  ⁢                                                                          ⁢                  n                                                      ⁢                                          sgn                ⁡                                  (                                      V                                          mn                      ′                                                              (                                              i                        -                        1                                            )                                                        )                                            ×                                                min                                                            n                      ′                                        ∈                                                                  N                        ⁡                                                  (                          m                          )                                                                    ⁢                      \                      ⁢                                                                                          ⁢                      n                                                                      ⁢                                                                                                V                                              mn                        ′                                                                    (                                                  i                          -                          1                                                )                                                                                                  .                                                                                        (        7        )            
The normalized min-sum decoding method performs near to that of conventional BP when decoding regular LDPC codes. Nevertheless, for decoding irregular LDPC codes, which are preferred for many applications, the gap between the performance of conventional normalized min-sum decoding and that of BP is large.
Therefore is desired to improve the normalized min-sum decoding method for all LDPC codes.